﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace IOP.Models.Tree.BinaryTree
{
    /// <summary>
    /// 二叉搜索树
    /// </summary>
    /// <typeparam name="TKey"></typeparam>
    /// <typeparam name="TValue"></typeparam>
    public class BinarySearchTree<TKey, TValue> : IBinaryTree<TKey, TValue>
        where TKey : IComparable<TKey>
    {

        /// <summary>
        /// 根节点
        /// </summary>
        public BinaryTreeNode<TKey, TValue> Root { get; set; } = null;

        /// <summary>
        /// 树节点数量
        /// </summary>
        public int Count { get; set; } = 0;

        /// <summary>
        /// 索引节点
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public TValue this[TKey key] => Get(key);

        /// <summary>
        /// 构造函数
        /// </summary>
        public BinarySearchTree() { }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="root">根节点</param>
        public BinarySearchTree(BinaryTreeNode<TKey, TValue> root)
        {
            Root = root;
        }

        /// <summary>
        /// 插入新的节点
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public virtual void Put(TKey key, TValue value)
        {
            BinaryTreeNode<TKey, TValue> newNode = new BinaryTreeNode<TKey, TValue>(key, value);
            if (Root == null)
            {
                Root = newNode;
                Count = 1;
            }
            else Root = Put(Root, key, value);
        }
        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="current"></param>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        private BinaryTreeNode<TKey, TValue> Put(BinaryTreeNode<TKey, TValue> current, TKey key, TValue value)
        {
            if (current == null)
            {
                current = new BinaryTreeNode<TKey, TValue>(key, value);
                Count++;
            }
            else
            {
                int cmp = key.CompareTo(current.Key);
                if (cmp == 1)
                {
                    current.Right = Put(current.Right, key, value);
                    current.Right.Parent = current;
                }
                else if (cmp == -1)
                {
                    current.Left = Put(current.Left, key, value);
                    current.Left.Parent = current;
                }
                else if (cmp == 0) current.Value = value;
            }
            current.Height = Math.Max(GetNodeHeight(current.Left), GetNodeHeight(current.Right)) + 1;
            return current;
        }

        /// <summary>
        /// 删除
        /// </summary>
        /// <param name="key"></param>
        public virtual void Delete(TKey key)
        {
            if (Root == null) throw new NullReferenceException("No data in this tree");
            if (key == null) throw new ArgumentNullException("key", "key is null");
            Root = Delete(Root, key);
        }
        /// <summary>
        /// 删除函数的递归方法
        /// </summary>
        /// <returns></returns>
        private BinaryTreeNode<TKey, TValue> Delete(BinaryTreeNode<TKey, TValue> current, TKey key)
        {
            if (current == null) return null;
            var cmp = key.CompareTo(current.Key);
            if (cmp == -1) current.Left = Delete(current.Left, key);
            else if (cmp == 1) current.Right = Delete(current.Right, key);
            else
            {
                if (current.Right == null)
                {
                    if (current.Left != null) current.Left.Parent = current.Parent;
                    Count--;
                    return current.Left;
                }
                if (current.Left == null)
                {
                    if (current.Right != null) current.Right.Parent = current.Parent;
                    Count--;
                    return current.Right;
                }
                var min = FindMin(current.Right);
                current.Key = min.Key;
                current.Value = min.Value;
                current.Right = Delete(current.Right, current.Key);
            }
            current.Height = Math.Max(GetNodeHeight(current.Left), GetNodeHeight(current.Right)) + 1;
            return current;
        }

        /// <summary>
        /// 搜索
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public TValue Get(TKey key)
        {
            if (Root == null) throw new NullReferenceException("No data in this tree");
            BinaryTreeNode<TKey, TValue> current = Root;
            while (true)
            {
                if (key.CompareTo(current.Key) == -1)
                {
                    if (current.Left == null) break;
                    current = current.Left;
                }
                else if (key.CompareTo(current.Key) == 1)
                {
                    if (current.Right == null) break;
                    current = current.Right;
                }
                else return current.Value;
            }
            if (key.CompareTo(current.Key) != 0) return default;
            return current.Value;
        }

        /// <summary>
        /// 是否包含某个节点
        /// </summary>
        /// <param name="key"></param>
        /// <param name="result"></param>
        /// <returns></returns>
        public bool Contains(TKey key, out TValue result)
        {
            if (key == null) throw new ArgumentNullException("key", "key is null");
            if (Root == null) throw new NullReferenceException("No data in this tree");
            result = default;
            BinaryTreeNode<TKey, TValue> current = Root;
            while (true)
            {
                if (key.CompareTo(current.Key) == -1)
                {
                    if (current.Left == null) break;
                    current = current.Left;
                }
                else if (key.CompareTo(current.Key) == 1)
                {
                    if (current.Right == null) break;
                    current = current.Right;
                }
                else
                {
                    result = current.Value;
                    return true;
                }
            }
            if (key.CompareTo(current.Key) != 0) return false;
            return false;
        }

        /// <summary>
        /// 清除
        /// </summary>
        public void Clear()
        {
            Root = null;
            Count = 0;
        }

        /// <summary>
        /// 寻找最大值
        /// </summary>
        /// <returns></returns>
        public TValue FindMax()
        {
            if (Root == null) throw new NullReferenceException("No data in this tree");
            var current = FindMax(Root);
            return current.Value;
        }
        /// <summary>
        /// 查找最大值(递归)
        /// </summary>
        /// <param name="current"></param>
        /// <returns></returns>
        protected internal BinaryTreeNode<TKey, TValue> FindMax(BinaryTreeNode<TKey, TValue> current)
        {
            if (current.Right == null) return current; ;
            return FindMax(current.Right);
        }

        /// <summary>
        /// 寻找最小值
        /// </summary>
        /// <returns></returns>
        public TValue FindMin()
        {
            if (Root == null) throw new NullReferenceException("No data in this tree");
            var current = FindMin(Root);
            return current.Value;
        }
        /// <summary>
        /// 查找最小值(递归)
        /// </summary>
        /// <param name="current"></param>
        /// <returns></returns>
        protected internal BinaryTreeNode<TKey, TValue> FindMin(BinaryTreeNode<TKey, TValue> current)
        {
            if (current.Left == null) return current;
            return FindMin(current.Left);
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Node<TKey, TValue>> PreOrder()
        {
            if (Root != null) return PreOrder(Root);
            else return new List<Node<TKey, TValue>>();
        }
        /// <summary>
        /// 先序遍历递归方法
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private IEnumerable<Node<TKey, TValue>> PreOrder(BinaryTreeNode<TKey, TValue> root)
        {
            List<Node<TKey, TValue>> elements = new List<Node<TKey, TValue>>();
            if (root != null)
            {
                elements.Add(root);
                elements.AddRange(PreOrder(root.Left));
                elements.AddRange(PreOrder(root.Right));
            }
            return elements;
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Node<TKey, TValue>> InOrder()
        {
            if (Root != null) return InOrder(Root);
            else return new List<Node<TKey, TValue>>();
        }
        /// <summary>
        /// 中序遍历递归方法
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private IEnumerable<Node<TKey, TValue>> InOrder(BinaryTreeNode<TKey, TValue> root)
        {
            List<Node<TKey, TValue>> elements = new List<Node<TKey, TValue>>();
            if (root != null)
            {
                elements.AddRange(InOrder(root.Left));
                elements.Add(root);
                elements.AddRange(InOrder(root.Right));
            }
            return elements;
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Node<TKey, TValue>> PostOrder()
        {
            if (Root != null) return PostOrder(Root);
            else return new List<Node<TKey, TValue>>();
        }
        /// <summary>
        /// 后序遍历递归方法
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private IEnumerable<Node<TKey, TValue>> PostOrder(BinaryTreeNode<TKey, TValue> root)
        {
            List<Node<TKey, TValue>> elements = new List<Node<TKey, TValue>>();
            if (root != null)
            {
                elements.AddRange(PostOrder(root.Left));
                elements.AddRange(PostOrder(root.Right));
                elements.Add(root);
            }
            return elements;
        }

        /// <summary>
        /// 比较Key值
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        protected internal int CompareKey(BinaryTreeNode<TKey, TValue> left, BinaryTreeNode<TKey, TValue> right)
        {
            return left.Key.CompareTo(right.Key);
        }

        /// <summary>
        /// 实现IEnumerable接口
        /// </summary>
        /// <returns></returns>
        public virtual IEnumerator<Node<TKey, TValue>> GetEnumerator()
        {
            foreach (var item in InOrder())
            {
                yield return item;
            }
        }

        /// <summary>
        /// 实现IEnumerable接口
        /// </summary>
        /// <returns></returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            foreach (var item in InOrder())
            {
                yield return item;
            }
        }

        /// <summary>
        /// 获取当前节点的高(当节点为空时返回0)
        /// </summary>
        /// <param name="current"></param>
        /// <returns></returns>
        protected internal int GetNodeHeight(BinaryTreeNode<TKey, TValue> current)
        {
            if (current != null) return current.Height;
            else return 0;
        }
    }
}
